#include<iostream>
#include<vector>
using namespace std;
/*
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
解题思路：
该题目是一个完全背包问题，dp[j]表示装满背包所需要的最少的物品数，
则有dp[j] = min(dp[j-nums[i]]+1,dp[j])
*/
int min(int a,int b)
{
    if(a<b)
        return a;
    else 
        return b;
}
int dp(vector<int> coins,int amount)
{
    //初始化dp数组
    vector<int> dp(amount+1,INT_MAX);
    dp[0] = 0;
    cout<<dp[0]<<endl;
    //先遍历物品再遍历背包，且背包为正序遍历
    for(int i=0;i<coins.size();i++)
    {
        for(int j=coins[i];j<=amount;j++)
        {
            dp[j] = min(dp[j-coins[i]]+1,dp[j]);
            cout<<dp[j]<<" ";
        }
        cout<<endl;
    }
    return dp[amount];
}

int main()
{
    cout<<"enter a amount:"<<endl;
    int amount;
    cin>>amount;
    cout<<"enter number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter coins:"<<endl;
    vector<int> coins(number);
    for(int i=0;i<number;i++)
    {
        cin>>coins[i];
    }
    cout<<dp(coins,amount);
}